package q60_getPermutation;

import java.util.Arrays;

public class Solution_1 {
    int[] resNums;
    int count = 0;// 记录数字位数
    int num = 0;// 记录当前数字
    int index = 0;// 记录到数组中的序号

    /*
    为了求出全排列中按照大小排列第K位的数
    这里使用了暴力解法
    结合46题进行 全排列 然后放入一个数组中
    排序后即可得到结果
     */
    public String getPermutation(int n, int k) {
        int sumNums = 1, rank = n;
        // 先得到阶乘的值 用来初始化数组的容量
        // n个数排列有n!个可能
        while (rank >= 1) {
            sumNums = sumNums * rank;
            rank--;
        }
        resNums = new int[sumNums];
        boolean[] used = new boolean[n + 1];
        // 标准的递归解法
        dfs(n, used);
        Arrays.sort(resNums);
        return String.valueOf(resNums[k - 1]);

    }

    private void dfs(int n, boolean[] used) {
        if (count == n){
            resNums[index] = num;
            index++;
            return;
        }

        // 注意 这里的i每次都要从0开始 所以不需要index了
        for (int i = 1; i <= n; i++) {
            // 数字没有用过才能够继续 用过的数字则不能再使用
            if (!used[i]) {
                used[i] = true;
                // 加入的操作逻辑
                num = num * 10 + i;
                count++;

                dfs(n, used);

                used[i] = false;
                num = (num - i) / 10;
                count--;
            }
        }
    }
}
